import java.util.Arrays;


//重复的子字符串，如果要重复，那肯定主串的长度肯定是子串的倍数
public class repetitionSubString {
    public void repeat(String s){//时间复杂度O(n2)
        //暴力法，尝试每一种子串是否是重复的子串
        //可以通过子串和主串的长度进行剪枝
        //如果是成倍数的子串，需要循环 主串长度/子串长度 次，如果每一次循环
        char[] cs = s.toCharArray();
        for (int i=0;i<cs.length;i++){//只需要看i个子串就可以了
            int subLen = i+1;//子串的长度
            if(cs.length %subLen != 0 ||subLen>cs.length/2){//主串长度不能够整除子串长度，所以不可能是由子串重复形成的
                System.out.println("continue");
                continue;//也是进行剪枝
            }
            int loop = cs.length / subLen;//要进行循环多少次子串的比较
            int start = 0;//子串每次对比的主串的位置
            int startSub = 0;//子串的第一个位置，就是主串第一个位置
            //对比每一个子串长度的字符串是否相等
            while (loop>0){
                boolean flag = false;//表示这一次的匹配是否成功，因为需要跳出这个大的while循环，所以需要一个flag
                for(int j=0;j<subLen;j++){
                    if(cs[start++]!=cs[startSub++]){//只要有一次不相同，就说明不是由该子串重复构成的
                        flag = true;
                        break;
                    }
                }
                if (flag){
                    break;
                }
                loop--;//进入下一次子串对比
                startSub = 0;//下一次还是从子串的最开头进行比较
            }
            if(start==cs.length&&subLen!=cs.length){//说明走到了最后，是一个解
                System.out.println(s.substring(0,subLen));
            }
        }
    }
    public Boolean repeatNewOne(String s){//移动匹配，这个代码是最简洁的，可是没遇到过是真的不知道
        String ss = (s+s).substring(1,2*s.length()-1);
        System.out.println(ss);
        if(ss.indexOf(s)!=-1){
            return true;
        }
        return false;
    }

    public boolean repeatNewTwo(String s){//使用KMP算法计算，利用next数组
        //利用next数组找最长相等前后缀
        int[] next = getNext(s);
        int max = 0;
        for(int i=0;i<s.length();i++){
            if(next[i]>max){
                max = next[i];
            }
        }
        if(s.length() % (s.length()-max) ==0){//如果该子串长度能够整除主串长度，那么就是可重复子串
            System.out.println(s.substring(0,s.length()-max));//最小重复子串
            return true;
        }
        return  false;
    }
    public int[] getNext(String sub){
        int j=0;//前缀末尾
        char[] sb = sub.toCharArray();
        int[] next = new int[sub.length()];
        for (int i=1;i<sub.length();i++){//i是
            while (j>0 && sb[j]!=sb[i]){
                j = next[j-1];
            }
            if(sb[j]==sb[i]){
                j++;
                next[i] = j;
            }
        }
//        System.out.println(Arrays.toString(next));
        return next;
    }
    public static void main(String[] args) {
        var main = new repetitionSubString();
        String s = "abcabc";
        String sb = "ababab";
        String c = "aaaaaa";
        String d = "abcbabc";
//        main.repeat(s);
//        main.repeatNewOne(s);
        main.repeatNewTwo(c);
//        main.getNext(sb);
    }
}
